Subset Sum Problem

The Subset Sum Problem involves finding all possible combinations of elements in a given array such that their sum equals a specified target. This problem is a classic example of using backtracking for combinatorial exploration. It has variations based on whether duplicate elements are allowed in the input set and whether each element can be chosen more than once.

Definition

Given a set of integers and a target sum, the subset sum problem asks whether there is a subset of the numbers in the set that adds up to exactly the target sum.

Formally: For a set $S = \{s_1, s_2, \ldots, s_n\}$ of integers and a target sum $t$, determine if there exists a subset of $S$ whose sum is exactly $t$.

Problem Classification

• Computational Complexity: This problem is NP-complete, which implies that there is no known polynomial-time algorithm to solve it for all cases. However, there are approaches that can solve it efficiently for specific instances or with approximation.
• Decision Problem: The subset sum problem is commonly expressed as a decision problem, where the goal is to decide whether a solution exists, rather than finding the solution itself.

Case without Duplicate Elements

Problem Statement

Given an array of positive integers nums and a target positive integer target, find all combinations where the sum equals the target. The array contains no duplicates, and each element can be used multiple times.

Reference Permutation Solution

The backtracking approach for this problem can be visualized as a series of choices, each updating an "element sum". When the sum equals the target, the subset is recorded. Elements can be chosen multiple times, which differentiates it from permutations where elements are used once.

Example

For nums = [2, 3, 6, 7] and target = 7, valid combinations are [[7], [2, 2, 3]].

Code Implementation

Here's a basic Python implementation:

def backtrack(state, target, total, choices, res):
    if total == target:
        res.append(list(state))
        return
    for i in range(len(choices)):
        if total + choices[i] > target:
            continue
        state.append(choices[i])
        backtrack(state, target, total + choices[i], choices, res)
        state.pop()

def subset_sum_i_naive(nums, target):
    state, total, res = [], 0, []
    backtrack(state, target, total, nums, res)
    return res

Optimization: Duplicate Subset Pruning

To avoid duplicate subsets (e.g., [2, 5] and [5, 2] being considered different), it's necessary to prune the search tree and deduplicate results, which can be achieved by sorting nums and ensuring choices in subsequent rounds do not backtrack to earlier indices.

def backtrack(state, target, choices, start, res):
    if target == 0:
        res.append(list(state))
        return
    for i in range(start, len(choices)):
        if target - choices[i] < 0:
            break
        state.append(choices[i])
        backtrack(state, target - choices[i], choices, i, res)
        state.pop()

def subset_sum_i(nums, target):
    nums.sort()
    res = []
    backtrack([], target, nums, 0, res)
    return res

Considering Cases with Duplicate Elements

Problem Statement

When the input array nums may contain duplicates, and each element can be chosen only once, it introduces the possibility of generating duplicate subsets from different recursive paths.

Example

For nums = [10, 1, 2, 7, 6, 1, 5] and target = 8, one might unintentionally produce duplicates like [[1, 7], [7, 1]].

Solution: Pruning Equal Elements

This involves modifying the backtracking approach to skip duplicate elements in the same recursive branch by using an index start and checking for repeated elements.

Code Implementation

def backtrack(state, target, choices, start, res):
    if target == 0:
        res.append(list(state))
        return
    for i in range(start, len(choices)):
        if target - choices[i] < 0:
            break
        if i > start and choices[i] == choices[i - 1]:
            continue
        state.append(choices[i])
        backtrack(state, target - choices[i], choices, i + 1, res)
        state.pop()

def subset_sum_ii(nums, target):
    nums.sort()
    res = []
    backtrack([], target, nums, 0, res)
    return res